// POJ 3264

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;

template <int N>
struct Log2_floor
{
	enum
	{
		res = Log2_floor<(N >> 1)>::res + 1
	};
};

template <>
struct Log2_floor<1>
{
	enum
	{
		res = 0
	};
};

// 0-based
template <typename T, int MaxIntervalLength, typename _Compare = std::less<T> >
class SparseTable
{
public:
	SparseTable()
	{
	}

	// get or set the value
	T &at(int i)
	{
		return st[0][i];
	}

	// interval length
	void preprocessST(int n)
	{
		for (int i = 1; (1 << i) <= n; i++)
			for (int j = 0; j + (1 << i) - 1 < n; j++) {
				T &leftv = st[i - 1][j];
				T &rightv = st[i - 1][j + (1 << (i - 1))];
				st[i][j] = (comp(leftv, rightv) ? leftv : rightv);
			}
	}

	T queryExtremeValue(int p, int q)
	{
		int z = log2(q - p + 1);
		int r = q - (1 << z) + 1;
		if (comp(st[z][p], st[z][r]))
			return st[z][p];
		return st[z][r];
	}

private:
	// the floor integer of log2(val)
	int log2(int val)
	{
		int ans = -1;
		while (val != 0)
		{
			val >>= 1;
			ans++;
		}
		return ans;
	}

private:
	T st[Log2_floor<MaxIntervalLength>::res + 1][MaxIntervalLength];
	// comparer
	_Compare comp;
};

SparseTable<int, 50000, less<int> > stMin;
SparseTable<int, 50000, greater<int> > stMax;

int main()
{
	int n;
	int q;
	scanf("%d%d", &n, &q);
	for (int i = 0; i < n; i++)
	{
		int temp;
		scanf("%d", &temp);
		stMin.at(i) = temp;
		stMax.at(i) = temp;
	}
	stMin.preprocessST(n);
	stMax.preprocessST(n);
	for (int i = 0; i < q; i++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		int maxVal = stMax.queryExtremeValue(x - 1, y - 1);
		int minVal = stMin.queryExtremeValue(x - 1, y - 1);
		printf("%d\n", maxVal - minVal);
	}

	system("pause");
	return 0;
}



/* deprecated
// 0-based
template <typename T, int MaxIntervalLength, typename _Compare = std::less<T> >
class SparseTable
{
public:
	SparseTable()
	{
		A.resize(MaxIntervalLength);
		int z = log2(MaxIntervalLength);
		M.resize(MaxIntervalLength);
		for (int i = 0; i < MaxIntervalLength; i++)
		{
			M[i].resize(z);
		}
	}

	// interval length
	void init(int n)
	{
		for (int i = 0; i < n; i++)
		{
			M[i][0] = i;
		}
	}

	// get or set the value
	T &at(int i)
	{
		return A[i];
	}

	// interval length
	void preprocessST(int n)
	{
		for (int j = 1; (1 << j) <= n; j++)
		{
			for (int i = 0; i + (1 << j) - 1 < n; i++)
			{
				int &leftIdx = M[i][j - 1];
				int &rightIdx = M[i + (1 << (j - 1))][j - 1];
				if (comp(A[leftIdx], A[rightIdx]))
					M[i][j] = leftIdx;
				else
					M[i][j] = rightIdx;
			}
		}
	}
	int queryExtremeValueIdx(int p, int q)
	{
		int z = log2(q - p + 1);
		int r = q - (1 << z) + 1;
		if (comp(A[M[p][z]], A[M[r][z]]))
			return M[p][z];
		else
			return M[r][z];
	}
private:
	// the floor integer of log2(val)
	int log2(int val)
	{
		int ans = -1;
		while (val != 0)
		{
			val >>= 1;
			ans++;
		}
		return ans;
	}

private:
	// original interval, from input
	vector<T> A;
	// 2 dimensional array
	vector<vector<int> > M;
	// comparer
	_Compare comp;
};
*/
